import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/23 9:51
 * @description 二分查找
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int maxValue(int n, int index, int maxSum) {
        long L = index + 1, R = n - index;
        // 最右边界，所有的位置至少为1
        long l = 1, r = maxSum - n + 1;
        long ans = 0;
        while (l <= r) {
            long mid = l + ((r - l) >> 1);
            long total = sum(L, R, mid);
            if (total <= maxSum) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return (int) ans;
    }

    private long sum(long L, long R, long mid) {
        return this.sum(L, mid) + this.sum(R, mid) - mid;
    }

    private long sum(long L, long mid) {
        return mid >= L ? ((mid - L + 1) + mid) * L / 2 : (1 + mid) * mid / 2 + L - mid;
    }
}
